package com.zxy.javaarithmetic.chapter_2_LinkList;

import java.util.Stack;

/*
 *  @项目名：  study
 *  @包名：    com.zxy.javaarithmetic.chapter_2_LinkList
 *  @文件名:   P_10_AddList
 *  @创建者:   zhangxy
 *  @创建时间:  2018/12/27 15:45
 *  @描述：    两个链表相加,例如 9->3->7 和 6->3 相加之后结果为 1->0->0->0
 *            方法一:把两个链表转成整数，相加之后再转成链表，缺点是链表可能很长转成系统的int类型可能会溢出
 *            方法二:把两个链表逆序，然后依次相加，把相加的结果节点组成链表
 *            方法三:利用栈结果，操作过程和方法二一样
 */
public class P_10_AddList {

	public static void main(String[] args) {
		Node head1 = LinkListUtils.getNode(3);
		Node head2 = LinkListUtils.getNode(2);

		LinkListUtils.printRingNode(head1);
		LinkListUtils.printRingNode(head2);

		LinkListUtils.printRingNode(addList2(head1, head2));

	}

	private static Node reverseList(Node head) {
		Node pre = null;
		Node next = null;

		while (head != null) {
			next = head.next;
			head.next = pre;
			pre = head;
			head = next;
		}
		return pre;
	}

	/**
	 * 方法二：逆序相加法
	 * 注意：逆序链表，计算完结果之后要记得恢复原状
	 * @param head1
	 * @param head2
	 */
	private static Node addList1(Node head1, Node head2) {
		Node re1 = head1 = reverseList(head1);
		Node re2 = head2 = reverseList(head2);
		Node result = null;
		Node node;
		int ca = 0;
		int sum;
		int i;
		int j;

		while (re1 != null || re2 != null) {
			i = re1 == null ? 0 : re1.value;
			j = re2 == null ? 0 : re2.value;

			sum = i + j + ca;
			ca = sum / 10;
			int value = sum % 10;
			if (result == null) {
				result = new Node(value);
			} else {
				node = new Node(value);
				node.next = result;
				result = node;
			}

			re1 = re1 == null ? null : re1.next;
			re2 = re2 == null ? null : re2.next;
		}

		if (ca == 1 || ca == 2) {
			node = new Node(ca);
			node.next = result;
			result = node;
		}

		//将链表恢复原状
		reverseList(head1);
		reverseList(head2);

		return result;
	}

	/**
	 * 利用栈完成数相加，然后生成链表
	 * @param head1
	 * @param head2
	 * @return
	 */
	private static Node addList2(Node head1, Node head2) {
		Stack<Integer> stack1 = new Stack<>();
		Stack<Integer> stack2 = new Stack<>();
		Node pre = null;
		Node node;
		int ca = 0;
		int sum;
		int i;
		int j;

		Node cur = head1;
		while (cur != null) {
			stack1.add(cur.value);
			cur = cur.next;
		}

		cur = head2;
		while (cur != null) {
			stack2.add(cur.value);
			cur = cur.next;
		}

		while (!stack1.isEmpty() || !stack2.isEmpty()) {
			i = stack1.isEmpty() ? 0 : stack1.pop();
			j = stack2.isEmpty() ? 0 : stack2.pop();
			sum = i + j + ca;
			ca = sum / 10;

			int value = sum % 10;
			if (pre == null) {
				pre = new Node(value);
			} else {
				node = new Node(value);
				node.next = pre;
				pre = node;
			}
		}

		if (ca == 1 || ca == 2) {
			node = new Node(ca);
			node.next = pre;
			pre = node;
		}

		return pre;
	}

}
